package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         34,
		Discription: "在有序数组中查找指定元素的第一个和最后一个位置",
		Level:       2,
		Labels: map[string]int{
			"二分查找": 1,
		},
	})
}

// 查找目标值的开始位置和结束位置
func SearchRange(nums []int, target int) []int {
	n := len(nums)
	if n == 0 {
		return []int{-1, -1}
	}

	findLeft := func() int {
		left := 0
		right := n - 1
		for left <= right {
			mid := left + (right-left)/2
			//排除特殊情况：左边界、左边界前一个、数组第0个
			if nums[mid] == target && (mid == 0 || nums[mid-1] != target) {
				return mid
			}
			if nums[mid] < target {
				if mid == n-1 {
					return -1
				} else if nums[mid+1] == target {
					return mid + 1
				}
			}

			if nums[mid] < target {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}

		return -1
	}

	findRight := func() int {
		left := 0
		right := n - 1
		for left <= right {
			mid := left + (right-left)/2
			//排除特殊情况：右边界、右边界后一个、数组最后一个
			if nums[mid] == target && (mid == n-1 || nums[mid+1] != target) {
				return mid
			}
			if nums[mid] > target {
				if mid == 0 {
					return -1
				} else if nums[mid-1] == target {
					return mid - 1
				}
			}

			if nums[mid] <= target {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}

		return -1
	}

	return []int{findLeft(), findRight()}
}
